package T41_T50;
import datastructure.TreeNode;
public class T49 {
    /**
     * 思路：1 遍历二叉树，寻找p和q的位置，如果p，q在异侧，返回当前结点node
     * 2 如果左边为null，右边不为null。则说明p，q都在右侧，此时right即为公共祖先
     * 3 右边是null，左边不为null同理
     * 4 如果都为null，说明左右都不存在p，q返回null
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null||root==p||root==q)return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left==null)return right;
        if (right==null)return left;
        return root;    //左右都不为null，直接返回当前结点
    }
}
